#!/usr/bin/env python

import numpy
import scipy
import Graph
import random
# import timeit
import cProfile
import pstats
import mail

class TrafficRank(object):
	def __init__(self, g = ''):
		print 'Initializating TrafficRank...'
		self.epi1 = 1e-4
		self.epi2 = 1e-4
		self.augmented = 0
		self.alpha = 0.3
		self.P = []
		self.SP = []

		if g != '':
			self.graph = g

	def __delf__(self):
		print 'Deleting TrafficRank...'

	def LoadGraph(self, g):
		self.graph = g
		self.nOfNode = g.Len()

	def SCTest(self):
		'''This is just a stub...'''
		print 'Entering SCTest...'
		return 0

	def GetAugMat(self, A, B, C, D):
		D = scipy.array([[D]])
		# print D.shape
		A = numpy.concatenate( [A, B], axis = 1 )
		tmp = numpy.concatenate( [C, D], axis = 1 )
		return numpy.concatenate( [A, tmp], axis = 0 )

	def GetStaProb(self):
		'''Get the Static Probability Distribution'''
		self.SP = scipy.sum(self.P, axis=0)
		# self.SP.shape = (1, self.nOfNode)
		self.SP = self.SP.reshape(-1,)
		# print self.SP
		return self.SP	

	def GetRank(self):
		ascentRank = numpy.argsort(self.SP)
		# print 'ascentRank'
		# print ascentRank
		# print '----------'
		# print ascentRank[0, :]
		# print '------------'
		rank = ascentRank[::-1] 
		# Index Start From 0, adjust it to start from 1
		return rank + 1

		

	# def BalanceMat(self, a, Z):
	#         A = scipy.diagflat(a)
	#         M = self.graph.Multiply( 1 / Z )
	#         invA = scipy.diagflat(1/a)
	# 
	#         P = numpy.dot(A, M)
	#         P = numpy.dot(P, invA)

	#         pho = scipy.sum(P, axis=0)
	#         delta = scipy.sum(P, axis=1)
	#         yita = numpy.sqrt( pho / delta)

		# print yita
	#         if numpy.isnan(sum(yita)):
	#                 raise NameError('Nan Error')


	#         if ( max( abs(yita - 1)) < self.epi1 ):
	#                 print 'Matrix Balancing Fnished'
	#                 endFlag = 1
	#         else:
	#                 endFlag = 0
	#                 yita.shape = (self.nOfNode, 1)
	#                 a = a * yita	

	#         return (a, P, endFlag)


	def BalanceAugMat(self, a, m, n, Z):
		# print 'Balance Aug Mat'
		# print a, m, n, Z
		A = scipy.diagflat(a)
		M = self.graph.Multiply( 1 / Z )
		invA = scipy.diagflat(1/a)

		M_bar = self.GetAugMat(M, scipy.ones( (self.nOfNode, 1)), scipy.ones( (1, self.nOfNode) ), 0)	

		A_bar = self.GetAugMat(A, scipy.zeros( (self.nOfNode, 1) ), scipy.zeros( (1, self.nOfNode) ), m)
		B_bar = self.GetAugMat(invA, scipy.zeros( (self.nOfNode, 1) ), scipy.zeros( (1, self.nOfNode) ), n)

		P_bar = numpy.dot(A_bar, M_bar)
		P_bar = numpy.dot(P_bar, B_bar)

		P = P_bar[0:self.nOfNode, 0:self.nOfNode]	

		# pho_0 = scipy.sum(P_bar, axis=0)
		# delta_0 = scipy.sum(P_bar, axis=1)
		pho_0 = scipy.sum(P_bar, axis=1)
		delta_0 = scipy.sum(P_bar, axis=0)

		pho = pho_0[0:self.nOfNode]	
		delta = delta_0[0:self.nOfNode]
		phoLast = pho_0[-1]
		deltaLast = delta_0[-1]
	
		# yita = numpy.sqrt( pho / delta)	
		yita = numpy.sqrt( delta / pho )	

		if numpy.isnan(numpy.sum(yita)):
			raise ValueError('Nan Error')
	
		if all([  max(abs(yita-1)) < self.epi1,  abs(phoLast - (1.0 -self.alpha)) <  self.epi1, abs(deltaLast -(1.0 -self.alpha) ) < self.epi1 ]):
			endFlag = 1
		else:
			endFlag = 0
			yita = yita.reshape(-1, 1)
			a = numpy.multiply(a,  yita)
			# m = m * numpy.sqrt(phoLast / deltaLast)
			# n = n / numpy.sqrt( phoLast / deltaLast )
			# print m, n

			m = m * (1.0 - self.alpha) / phoLast
			n = n * (1.0 - self.alpha) / deltaLast	
			# print m, n

		return (a, m, n, P, endFlag)





	def Exec(self):
		'''Implementation of Traffic Rank Algorithm'''

		if ~self.SCTest():
			print 'The original graph do not satisfy strong connected property, a virtual node will be added...'
			self.augmented = 1
			
		lbd = scipy.zeros( (self.nOfNode, 1), int )
		a = scipy.exp(-1 * lbd)
		outNum = 0
		m = 1.0 / self.nOfNode	
		n = 1.0 / self.nOfNode


		while 1:
			outNum += 1
			print 'Outside Loop Iterate For ' + str(outNum) + 'th times'
			lbd = -1 * scipy.log(a)

			lbd_i = scipy.tile(lbd, (1, self.nOfNode) )
			lbd_j = scipy.tile(lbd.T, (self.nOfNode, 1))
			Z = scipy.sum( self.graph.Multiply( scipy.exp(lbd_j - lbd_i) ))
			# Z = 1

			if self.augmented:
				# Inside Loop To Balance the Matrix
				inNum = 0
				while 1:
					# Input is a, m, n, P Output is a, m, n, P, endFlag
					inNum += 1
					# print '+++++++++'
					# print m, n
					# print '++++++++++'
					print 'Inside Loop iter for ' + str(inNum) + 'th times'
					(a, m, n, P, endFlag) = self.BalanceAugMat(a, m, n, Z)
					# print '---------'
					# print m, n
					# print '----------'
					if endFlag == 1:
						print 'Matrix Balancing Finished...'
						break
			else:
				inNum = 0
				while 1:
					inNum += 1
					print 'Inside Loop iter for ' + str(inNum) + 'th times'
					(a, P, endFlag) = self.BalanceAugMat(a, Z)
					if endFlag == 1:
						print 'Matrix Balancing Finished...'
						break

				
			print 'Sum of Probability: ' + str(numpy.sum(P))
			# break
			if abs(numpy.sum(P) - 1) < self.epi2:
				# print 'Program Finished'
				# print 'P:'
				# print P
				break

		self.P = P


def Test():
	# g = Graph.Graph(5)
	# g.AddLink(1, 2)
	# g.AddLink(1, 4)
	# g.AddLink(2, 2)
	# g.AddLink(2, 3)
	# g.AddLink(2, 5)
	# g.AddLink(3, 1)
	# g.AddLink(3, 3)
	# g.AddLink(3, 5)
	# g.AddLink(4, 2)
	# g.AddLink(4, 3)
	# g.AddLink(4, 4)
	# g.AddLink(5, 1)
	# g.AddLink(5, 2)
	# g.AddLink(5, 3)
	# g.AddLink(5, 5)
	n = 1e2
	g = Graph.Graph(n)
	for i in (range(n) ):
		for j in (range(n)):
			if i == j:
				continue

			if random.random() < 0.5 :
				g.AddLink(i, j)
	# print g
	# g.Print()
	# print g.Shape()
	# print 'Start to LoadGraph'
	tr.LoadGraph(g)
	# print 'Start to Exec'
	tr.Exec()
	# print 'Stationary Probabiliy is:'
	# print tr.GetStaProb()
	# print 'shape...'
	# print tr.GetStaProb().shape

		
		
if __name__ == "__main__":
	tr = TrafficRank()

	n = 20 
	g = Graph.Graph(n)
	for i in (range(n) ):
		for j in (range(n)):
			if i == j:
				continue

			if random.random() < 0.3:
				g.AddLink(i, j)
	# g = Graph.Graph(5)
	# g.AddLink(1, 2)
	# g.AddLink(1, 4)
	# g.AddLink(2, 2)
	# g.AddLink(2, 3)
	# g.AddLink(2, 5)
	# g.AddLink(3, 1)
	# g.AddLink(3, 3)
	# g.AddLink(3, 5)
	# g.AddLink(4, 2)
	# g.AddLink(4, 3)
	# g.AddLink(4, 4)
	# g.AddLink(5, 1)
	# g.AddLink(5, 2)
	# g.AddLink(5, 3)
	# g.AddLink(5, 5)
	# print '---------------------------------'
	# print g

	tr.LoadGraph(g)
	try:
		tr.Exec()

		print '---------------------------------'
		print tr.GetStaProb()
		print '---------------------------------'
		print tr.GetRank()
		print '---------------------------------'
		# x
		# mail.SendTestResult('Simulation of Traffic Rank Success!')
	except:
		# mail.SendTestResult('Simulation of Traffic Rank Failed!')
		print 'fail'

	
		 
	# cProfile.run('tr.Exec()', 'trprof')
	# p = pstats.Stats('trprof')
	# p.strip_dirs().sort_stats(-1).print_stats()
	# p.sort_stats('time').print_stats(10)
	# Test()
	# t = timeit.Timer("Test()", "from __main__ import Test")
	# print t.timeit(100)
